// 第一个类型是基底的类型
// 第二个类型是指数的类型
// O(sqrt(P))预处理， O(1)算a^b次方
// 此模板基底和模数是固定的
template <class T, class V>
struct LightPower {
	using i64 = long long;

	LightPower(T base, V p) : base_(base), p_(p) {
		base_ %= p;
		Block_ = sqrtl(p) + 1;
		power1_.resize(Block_ + 1, 1);
		power2_.resize(Block_ + 1, 1);

		for (int i = 1; i <= Block_; i++) {
			power1_[i] = power1_[i - 1] * base % p;
		}
		for (int i = 1; i <= Block_; i++) {
			power2_[i] = power2_[i - 1] * power1_[Block_] % p;
		}

		phi_ = p;
		for (int i = 2; i <= Block_; i++) {
			if (p % i == 0) {
				phi_ = phi_ / i * (i - 1);
				while (p % i == 0) {
					p /= i;
				}
			}
		}
		if (p > 1) {
			phi_ = phi_ / p * (p - 1);
		}
	}

	i64 power(const i64 b) {
    b %= phi_;
		return power2_[b / Block_] * power1_[b % Block_] % p_;
	}

	int phi_, Block_;
	T base_;
	V p_;
	vector<i64> power1_, power2_;
};
int main() {
	LightPower<int, int> lp(3, 998244353);
	cout << lp.power(33);
	return 0;
}